package leetcode;


import java.util.*;

/**
 * 01 矩阵
 */
public class LeetCode542 {
    public int[][] updateMatrix(int[][] matrix) {
        if (matrix.length == 0) return matrix;
        int depth = 0;
        Set<String> visited = new HashSet<>();
        Queue<String> queue = new LinkedList<>();
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (matrix[i][j] == 0) {
                    queue.offer(i + ":" + j);
                    visited.add(i + ":" + j);
                }
            }
        }
        int[][] vector = new int[][]{{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
        queue.offer(null);
        while (!queue.isEmpty()) {
            String s = queue.poll();
            if (s == null) {
                depth++;
                if (queue.peek() != null) {
                    queue.offer(null);
                }
            } else {
                String[] xy = s.split(":");
                int x = Integer.parseInt(xy[0]);
                int y = Integer.parseInt(xy[1]);
                matrix[x][y] = depth;
                for (int[] i : vector) {
                    int r = x + i[0];
                    int c = y + i[1];
                    if (r >= 0 && r < matrix.length && c >= 0 && c < matrix[0].length && matrix[r][c] > matrix[x][y]) {
                        queue.offer(r + ":" + c);
                        visited.add(r + ":" + c);
                    }
                }
            }

        }
        return matrix;
    }
}